Міністерство освіти і науки України
Інститут прикладної математики та фундаментальних наук
Кафедра прикладної математики
Курсова робота
на тему:
„Автомати з магазинною пам’яттю”
Львів 2006 Вступ
У роботі розглядатимуться положення пов’язані з функціонуванням автоматів з магазинною пам’яттю, їхні види, побудова тощо.
Скінченні автомати можуть вирішувати лише ті завдання, які вимагають скінченого об’єму пам’яті. Але у компіляторах часто виникають задачі, які не можуть вирішуватися з такими обмеженнями. Наприклад, при обробці арифметичних виразів виникає задача перевірки балансу дужок: кількість лівих дужок повинна відповідати кількості правих. Кожна дужка у виразі має свою „роль”, тому використання скінченного автомата для таких задач не прийнятне, оскільки множина станів може бути нескінченною.
Для вирішення цієї та багатьох інших проблем компіляції, можуть використовуватись моделі потужніших автоматів. У них пам’ять скінченного автомата розширюється за рахунок додаткового механізму зберігання інформації. Один із методів – це використання магазина (або стека). Основна особливість магазинної пам’яті полягає в тому, що символи можна вносити у магазин і видаляти їх з нього по одному. При цьому видаляється завжди лише верхній символ, тобто символ, який був внесений у магазин останнім.
Однією з моделей автомата, в яких використовується магазинний принцип організації пам’яті, є автомат з магазинною пам’яттю (МП–автомат). У ньому дуже просто поєднується пам’ять скінченого автомата і магазинна пам’ять.
Як і у випадку скінченого автомата, обробка скінченого ланцюжка символів здійснюється за ряд простих кроків. На кожному кроці дії автомата конфігурація його пам’яті може змінюватись за рахунок:
переходу у новий стан;
заштовхування символу в магазин;
виштовхування символу з магазина;
зчитування символу зі вхідного ланцюжка.
Отже, наведено достатньо фактів, які підтверджують актуальність опрацювання питання про автомати з магазинною пам’яттю.
Базові означення МП–автоматів
Означення МП–автомата. Принцип роботи. Приклади.
Автомати з магазинною пам’яттю відомі також як МП–автомати.
Магазинний автомат – це зазвичай скінченний автомат, який називають керуючим, в якого, крім вхідного і вихідного каналів, є ще канал для роботи з магазином. Магазин являє собою пам'ять, яка має назву магазинної пам'яті, де може зберігається одне слово в деякому алфавіті. Цей алфавіт називається магазинним алфавітом і, взагалі кажучи, може відрізнятися від вхідного і вихідного алфавітів автомата. Магазин зручно зображати у вигляді послідовності чарунок пам’яті, перенумерованих числами натурального ряду і розміщених по вертикалі таким чином, що перша чарунка завжди стає верхньою. Слово із символів магазинного алфавіту розміщається у верхніх чарунках магазину, а решта заповнюється спеціальним порожнім символом, відмінним від символів алфавіту . Магазин може працювати в двох режимах: читання і запису. При читанні сприймається буква, що знаходиться в чарунці. При цьому буква витирається з цієї чарунки, а частина слова, що залишається в магазині, зміщується на одну чарунку вверх. В режимі запису, навпаки, слово, що зберігається в магазині, зміщується вниз на одну чарунку, а в чарунку, яка при цьому звільнилася, записується відповідний символ.
Означення. МП–автомат – це така сімка, де:
– скінчена множина станів
– скінчений вхідний алфавіт
– скінчений алфавіт магазинних станів
– функція переходів і виходів, яка відображає елементи декартового добутку
– початковий стан
– символ, який знаходиться в магазині в початковий момент (початковий символ)
– множина кінцевих станів.
На кожному кроці роботи МП–автомат може або занести щось в магазин, або взяти якесь значення з його вершини. Відмітимо, що МП–атомат може продовжувати працювати в випадку порожнього, звільненого магазину.
МП–автомат схожий до скінченного автомата, але відрізняється від останнього робочою пам’яттю – магазином, в який записуються символи із ще одного алфавіту – алфавіту маг...
